/**********************************************************

@description:
*File Name:rbtree_1.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Tue 06 May 2025 06:49:33 AM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define COLOR(x)         ((x)->color)
#define SET_COLOR(x,c)   ((x)->color=c)
#define PARENT(x)        (((x)->parent)?((tnode*)((x)->parent)):NULL)
#define SET_PARENT(x,p)  ((x)->parent=(p))
#define SET_BLACK(x)     ((x)->color=BLACK)
#define SET_RED(x)       ((x)->color=RED)
#define IS_BLACK(x)      ((x)->color==BLACK)
#define IS_RED(x)        ((x)->color==RED)

typedef enum color{
	RED=0,
	BLACK
}color;
typedef struct tnode{
	struct tnode *lchild,*rchild,*parent;
	color color;
	int key;
	void *pri_data;
}tnode;
typedef struct rbtree{
	struct tnode *root;
	int treesize;
}rbtree;
tnode* init_tnode(void* data){
	tnode* n=(tnode*)malloc(sizeof(tnode));
	if(!n){
		printf("init_tnode malloc error!\n");
		return NULL;
	}
	n->pri_data=data;
	n->lchild=n->rchild=n->parent=NULL;
	SET_RED(n);
	n->pri_data=data;
	if(data)
		n->key=*((int*)data);
	return n;
}
rbtree *init_rbtree(){
	rbtree * t=(rbtree *)malloc(sizeof(rbtree));
	if(!t){
		printf("init_rbtree malloc error!\n");
		return NULL;
	}
	t->root=NULL;
	t->treesize=0;
	return t;
}
void ll_rotate(tnode **root,tnode *x){
	tnode *y=x->rchild;
	x->rchild=y->lchild;
	if(y->lchild != NULL){
		y->lchild->parent=x;
	}
	y->parent=x->parent;
	if(x->parent==NULL){
		*root=y;
	}else if(x == x->parent->lchild){
		x->parent->lchild=y;
	}else{
		x->parent->rchild=y;
	}
	y->lchild=x;
	x->parent=y;
}
void rr_rotate(tnode **root,tnode *y){
	tnode *x=y->lchild;
	y->lchild=x->rchild;
	if(x->rchild != NULL){
		x->rchild->parent=y;
	}
	x->parent=y->parent;
	if(y->parent==NULL){
		*root=x;
	}else if(y == y->parent->lchild){
		y->parent->lchild=x;
	}else{
		y->parent->rchild=x;
	}
	x->rchild=y;
	y->parent=x;
}
void adjust_node(rbtree *tree,tnode *node){
	tnode *parent,*gparent;
	while(1){
		//while(parent=PARENT(node)&&IS_RED(parent)) why does this will cause to segmentation fault?
#if 1
		parent=PARENT(node);
		if(!parent)
			break;
		int ir=IS_RED(parent);
		if(!ir)
			break;
#endif
		gparent=PARENT(parent);
		if(parent==gparent->lchild){
			//No.1 uncle=red
			tnode *uncle=gparent->rchild;
			if(uncle && IS_RED(uncle)){
				SET_BLACK(parent);
				SET_BLACK(uncle);
				SET_RED(gparent);
				node=gparent;
				continue;
			}
			//no.2 uncle=black rson
			if(parent->rchild==node){
				node=parent;
				ll_rotate(&tree->root,parent);
			}else{
			//No.3 uncle=black lson
				SET_BLACK(parent);
				SET_RED(gparent);
				rr_rotate(&tree->root,gparent);
			}
		}else{
			//No.1 uncle=red
			tnode *uncle=gparent->lchild;
			if(uncle && IS_RED(uncle)){
				SET_BLACK(parent);
				SET_BLACK(uncle);
				SET_RED(gparent);
				node=gparent;
				continue;
			}
			//no.2 uncle=black rson
			if(parent->lchild==node){
				node=parent;
				rr_rotate(&tree->root,parent);
			}else{
			//No.3 uncle=black lson
				SET_BLACK(parent);
				SET_RED(gparent);
				ll_rotate(&tree->root,gparent);
			}
		}
	}
	SET_BLACK(tree->root);
}
void adjuse_erase(rbtree *tree,tnode *node,tnode *parent){
	tnode *other;
	while(!node || IS_BLACK(node) && node != tree->root){
		if(node==parent->lchild){
			other=parent->rchild;
			if(IS_RED(other)){
				//No.1 bro=red
				SET_BLACK(other);
				SET_RED(parent);
				ll_rotate(&tree->root,parent);
				other=parent->rchild;
			}
			if(!other->lchild || IS_BLACK(other->lchild) && !other->rchild || IS_BLACK(other->rchild)){
				//No.2 bro=black
				SET_RED(other);
				node=parent;
				parent=PARENT(node);
			}else{
				if(!other->rchild || IS_BLACK(other->rchild)){
					//No.3 bro=black,bro->lchild=red,bro->rchild=black
					SET_BLACK(other->lchild);
					SET_RED(other);
					rr_rotate(&tree->root,other);
					other=parent->rchild;
				}
				//No.4
				SET_COLOR(other,COLOR(parent));
				SET_BLACK(parent);
				SET_BLACK(other->rchild);
				ll_rotate(&tree->root,parent);
				node=tree->root;
				break;
			}
		}else{
			other=parent->lchild;
			if(IS_RED(other)){
				//No.1 bro=red
				SET_BLACK(other);
				SET_RED(parent);
				ll_rotate(&tree->root,parent);
				other=parent->lchild;
			}
			if(!other->lchild || IS_BLACK(other->lchild) && !other->rchild || IS_BLACK(other->rchild)){
				//No.2 bro=black
				SET_RED(other);
				node=parent;
				parent=PARENT(node);
			}else{
				if(!other->lchild || IS_BLACK(other->lchild)){
					//No.3 bro=black,bro->lchild=red,bro->rchild=black
					SET_BLACK(other->rchild);
					SET_RED(other);
					rr_rotate(&tree->root,other);
					other=parent->lchild;
				}
				//No.4
				SET_COLOR(other,COLOR(parent));
				SET_BLACK(parent);
				SET_BLACK(other->lchild);
				ll_rotate(&tree->root,parent);
				node=tree->root;
				break;
			}
		}
	}
	if(node){
		SET_BLACK(node);
	}

}
int insert(rbtree *tree,tnode *node){
	tnode *pre=NULL;
	tnode *cur=tree->root;
	while(cur != NULL){
		pre=cur;
		if(node->key < cur->key){
			cur = cur->lchild;
		}else{
			cur=cur->rchild;
		}
	}
	SET_PARENT(node,pre);
	if(pre){
		if(pre->key > node->key){
			pre->lchild=node;
		}else{
			pre->rchild=node;
		}
	}else{
		tree->root=node;
	}
	tree->treesize++;
	adjust_node(tree,node);
}
tnode* search(tnode *root,int key){
	if(!root || key==root->key)
		return root;
	if(key<root->key)
		return search(root->lchild,key);
	if(key>root->key)
		return search(root->rchild,key);
}
void erase_node(rbtree *tree,tnode *node){
	tnode *child,*parent;
	int color;
	//case 1
	if(node->lchild && node->rchild){
		tnode *rep=node;
		rep=rep->rchild;
		while(rep->lchild){
			rep=rep->lchild;
		}
		if(PARENT(node)){
			if(PARENT(node)->lchild==node){
				PARENT(node)->lchild=rep;
			}else{
				PARENT(node)->rchild=rep;
			}
		}else{
			tree->root=rep;
		}
		child=rep->rchild;
		parent=PARENT(rep);
		color=COLOR(rep);
		if(parent==node){
			parent=rep;
		}else{
			if(child){
				SET_PARENT(child,parent);
			}
			parent->lchild=child;
			rep->rchild=node->rchild;
			SET_PARENT(node->rchild,rep);
		}
		rep->parent=node->parent;
		rep->color=node->color;
		rep->lchild=node->lchild;
		node->lchild->parent=rep;
		if(color==BLACK){
			adjuse_erase(tree,child,parent);
		}
		free(node);
		node=NULL;
		return;
	}
	//case 2
	if(node->lchild){
		child=node->lchild;
	}else{
		child=node->rchild;
	}
	parent=node->parent;
	color=node->color;
	if(parent){
		if(parent->lchild==node){
			parent->lchild=child;
		}else{
			parent->rchild=child;
		}
	}else{
		tree->root=child;
	}
	if(color==BLACK){
		adjuse_erase(tree,child,parent);
	}
	free(node);
	node=NULL;
	//case 3
#if 0
	if(node==node->parent->lchild)
		node->parent->lchild=NULL;
	else
		node->parent->rchild=NULL;
	tree->treeseize--;
#endif
}
void erase_tree(rbtree *tree,int key){
	tnode *res=search(tree->root,key);
	if(res)
		erase_node(tree,res);
}
typedef void (*visit)(tnode*);
void pn(tnode* n){
	if(n)
		printf("%d:%s\n",*((int*)n->pri_data),n->color?"BLACK":"RED");
}
void preorder(tnode* t,visit v){
	v(t);
	if(t){
		preorder(t->lchild,v);
		preorder(t->rchild,v);
	}
}
void inorder(tnode* t,visit v){
	if(t){
		inorder(t->lchild,v);
		v(t);
		inorder(t->rchild,v);
	}
}
void postorder(tnode* t,visit v){
	if(t){
		postorder(t->lchild,v);
		postorder(t->rchild,v);
		v(t);
	}
}
void test(void);
int main(){
	int arr[]={10,40,30,60,90,70,20,50,80};
	int arr_len=sizeof(arr)/sizeof(int);
#if 0
	test();
#endif
#if 1
	rbtree *tree=init_rbtree();
	for(int i=0;i<arr_len;i++){
		tnode *n=init_tnode(arr+i);
		insert(tree,n);
	}
	inorder(tree->root,pn);
	printf("\n");
	preorder(tree->root,pn);
	printf("search:\n");
	printf("%d\n",search(tree->root,30)->key);
	erase_tree(tree,30);
	preorder(tree->root,pn);

	
#endif
}
void test(){
	int *a;
	a=(int*)malloc(sizeof(int));
	*a=11;
	tnode *n=NULL;
	printf("NULL:%p\n",n);
	n=init_tnode(a);
	printf("n:%p,n->parent:%p\n",n,PARENT(n));
	n->parent=n;
	printf("n:%p,n->parent:%p,key:%d\n",n,PARENT(n),n->key);
}
